Embodiments of the invention relate to methods and systems for predicting outcomes of branch instructions. In particular, embodiments of present invention relate to storing instructions from branch mis-predictions for use during subsequent branch mis-predictions.
A program may include a branch instruction at which, based on a branch condition, a process may proceed in one of multiple possible ways. For example, in a sequence of instructions, 1, 2, 3, 4, 5, where 5 is a branch instruction, instruction 5 may command the process to proceed sequentially to instructions 6, 7, 8, . . . or to jump ahead to instructions 100, 101, 102, . . . .
To avoid time delays, instructions are typically fetched from program memory ahead of time so that they are ready for use when they are needed in the processor pipeline. However, at a branch, the next instruction may be unknown until the branch instruction is executed. Therefore, subsequent instructions can not be fetched beforehand, thereby causing a time delay in the process pipeline.
To reduce such time delays, a branch predictor may be used to predict the outcome of a conditional branch. The predicted instructions at the branch are preemptively retrieved from program memory and temporarily stored in a program cache for easy access. A branch predictor may be static, using only the branch instructions themselves to determine the branch outcome or dynamic, also using historical statistics of the branch to determine the branch outcome.
However, branch predictors may perform poorly for some algorithms, e.g., predicting correctly at approximately 50% of branches and predicting incorrectly at approximately 50% of branches. Furthermore, some algorithms cannot benefit from dynamic branch prediction, e.g., when there is no correlation between a current branch decision and preceding branch decisions.
When a branch prediction is correct, the predicted instructions are immediately retrieved from the program cache. When the branch prediction is incorrect, the retrieved instructions are discarded and the processor must again retrieve the correct instructions from program memory using additional computational cycles. The additional computational cycles used to retrieve the correct instructions from program memory after a branch mis-prediction may be referred to as a branch mis-prediction penalty.
It will be appreciated that for simplicity and clarity of illustration, elements shown in the figures have not necessarily been drawn to scale. For example, the dimensions of some of the elements may be exaggerated relative to other elements for clarity. Further, where considered appropriate, reference numerals may be repeated among the figures to indicate corresponding or analogous elements.